package org.example.dynamic_planning;

public class Delete_two_strings {
    public static void main(String[] args) {
        //两个字符串的删除操作

        //给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
        //每步 可以删除任意一个字符串中的一个字符。
        String word1 = "sea";
        String word2 = "eat";
        int i = minDistance(word1, word2);
        System.out.println(i);
    }
    public static int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        char[] ch1 = word1.toCharArray();
        char[] ch2 = word2.toCharArray();
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (ch1[i-1] == ch2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return word1.length() + word2.length() - 2*dp[word1.length()][word2.length()];
    }
}
